﻿namespace Leetcode.N0115;
public class Solution
{
    public int NumDistinct(string s, string t)
    {
        if (s.Length == 0 || t.Length == 0)
        {
            return 0;
        }
        var tnum = new int[t.Length];
        var tindex = new Dictionary<char, IList<int>>();
        for (int i = 0; i < t.Length; i++)
        {
            if (!tindex.ContainsKey(t[i]))
            {
                tindex.Add(t[i], new List<int>());
            }
            tindex[t[i]].Add(i);
        }

        for (int i = 0; i < s.Length; i++)
        {
            if (!tindex.ContainsKey(s[i]))
            {
                continue;
            }
            var indexes = tindex[s[i]];
            for (int j = indexes.Count - 1; j >= 0; j--)
            {
                var index = indexes[j];
                if (index == 0)
                {
                    tnum[index]++;
                }
                else
                {
                    tnum[index] += tnum[index - 1];
                }
            }
        }

        return tnum[tnum.Length - 1];
    }
}
